package leetcode;

public class CountBits {

	public static void main(String[] args) {
		CountBits bits = new CountBits();
		int[] res = bits.countBits(1);
		int k = 1;
		for (int i = 0; i < res.length; i++) {
			if(i == Math.pow(2, k)){
				k++;
				System.out.println();
			}
			System.out.print(res[i] + " ");
		}
	}
	public int[] countBits(int num) {
        if(num < 0){
            return new int[]{};
        }
        if(num == 0){
            return new int[]{0};
        }
//        if(num == 1){
//            return new int[]{0, 1};
//        }
        int[] res = new int[num + 1];
        res[1] = 1;
        int k = 1;
        for(int i = 2; i <= num; i++){
            if(i == Math.pow(2, k + 1)){
                k++;
            }
            res[i] = res[i - (int)Math.pow(2, k)] + 1;
        }
        return res;
    }
}
